PESQUISA OPERACIONAL¶
MAXIMINIZAÇÃO¶
Exercício 2 (ENADE)¶
Uma fábrica produz dois refrigerantes: A e B. Para produzí-los, utilizam-se vários recursos, entre os quais os extratos e a água são os mais limitantes, devido a problemas ecológicos.
Para produzir um litro do refrigerante A, o processo envolve a dissolução de um pacote do extrato (denominado Delta)em um litro de água, além de outros recursos que não são limitantes.
Já a produção de um litro do refrigerante B, além da dissolução de um pacote de extrato (denominado Gama) em um litro de água, exige mais um litro de outros recursos para o processo de arrefecimento, além de outros recursos não limitantes.
Sabe-se que:
a) O lucro gerado por litro de A é R\$5, enquanto que o lucro por litro de B é R\$2.
b) O fornecedor de extratos só consegue entregar 3.000 pacotes de extrato Delta e 4.000 pacotes de extrato Gama, semanalmente.
c) Há umf ator ambiental limitante de 9.000 litros de água por semana.
Denominando de $X1$ a quantidade de litros de refrigerante A e $X2$, a quantidade de refrigerante B a serem produzidos, qual deverá ser o plano de produção semanal viável para gerar o maior lucro a essa fábrica, dentro das condições apresentadas?
Solução pelo Método Gráfico:¶
Função Objetivo:
Sujeito a
$ A(0,0) \quad\quad Z_{A} = 0$
$ B(3000,0) \quad\quad\quad Z_{B} = 5.3000 + 2.0 = 15.000$
$ C(3000,3000) \quad\quad Z_{C} = 5.3000 + 2.3000 = 21.000 $
$ D(1000,4000) \quad\quad Z_{D} = 5.1000 + 2.4000 = 13.000$
$ E(0,4000) \quad \quad \quad Z_{E} = 5.0 + 2.4000 = 8.000$
Solução pelo Método Simplex¶
1. Inserir as variáveis de folga
$ Z -5X_{1} - 2X_{2} = 0 $
$ X_{1} + f_{1} = 3000 $
$ X_{2} + f_{2} = 4000 $
$ X_{1} + 2X_{2} + f_{3} = 9000 $
2. Construção do Tabela inicial
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | -5 | -2 | 0 | 0 | 0 | 0 |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 |
| L4 | 0 | 1 | 2 | 0 | 0 | 1 | 9000 |
A linha L1 é referente a função objetivo (L). A linha L2 é a primeira variável de folga ($f_{1}$) e assim por diante.
3. Seleção da Coluna Pivô
A coluna pivô é coluna que tem o maior valor absoluta entre varáveis não básicas ($X_{1}$ e $X_{2}$).
Calcular a coluna Quociente dividindo os valores de LD pelos valores da colunas pivô.
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | Quociente | |
|---|---|---|---|---|---|---|---|---|
| L1 | 1 | -5 | -2 | 0 | 0 | 0 | 0 | - |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 | 3000 |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 | |
| L4 | 0 | 1 | 2 | 0 | 0 | 1 | 9000 | 9000 |
4. Seleção da Linha Pivô (LP)
A linha pivô é a que possui o menor valor de quociente.
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | Quociente | |
|---|---|---|---|---|---|---|---|---|
| L1 | 1 | -5 | -2 | 0 | 0 | 0 | 0 | - |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 | 3000 |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 | |
| L4 | 0 | 1 | 2 | 0 | 0 | 1 | 9000 | 9000 |
A interseção entre a coluna pivô e a linha pivô, indica o elemento pivô, que no presente caso é 1.
5. Calcular a Nova Linha Pivô (NLP)
$ NLP = \displaystyle\frac{1}{pivô}.LP$
Onde: $pivô$ = elemento pivô
$ NLP = \displaystyle\frac{1}{1}.(0,1,0,1,0,0,3000)$
$ NLP = (0,1,0,1,0,0,3000)$
6. Primeira Iteração
Mantem-se a nova linha pivô na tabele e calcula-se a nova linha 1 (L1).
$ NL1 = L1 - coeficiente \,da \,linha1 \,. NLP$
$NL1 = (1,-5,-2,0,0,0,0) - (-5) . (0,1,0,1,0,0,3000)$
$NL1 = (1,-5,-2,0,0,0,0) + (0,5,0,5,0,0,15000)$
$NL1 = (1, 0, -2, 5, 0, 0, 15000)$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | -2 | 5 | 0 | 0 | 15000 |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 |
| L3 | |||||||
| L4 |
Calcular as interações para a nova linha 3 (NL3) e a nova linha 4 (L4).
$NL3 = L3 - coeficiente \,da \,linha3 \,. NLP$
$NL3 = (0, 0, 1, 0, 1, 0, 4000) - 0 . (0,1,0,1,0,0,3000)$
$NL3 = (0, 0, 1, 0, 1, 0, 4000)$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | -2 | 5 | 0 | 0 | 15000 |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 |
| L4 |
$NL4 = L4 - coeficiente \,da \,linha4 \,. NLP$
$NL4 = (0,1,2,0,0,1,9000) - 1 \,. (0,1,0,1,0,0,3000)$
$NL4 = (0,1,2,0,0,1,9000) - (0,1,0,1,0,0,3000)$
$NL4 = (0,0,2,-1,0,1,6000)$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | -2 | 5 | 0 | 0 | 15000 |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 |
| L4 | 0 | 0 | 2 | -1 | 0 | 1 | 6000 |
O valor negativo -2 na variável não básica $X_{2}$ indica que a iteração ainda não acabou.
7. Preparação para Segunda Interação
A coluna da variável não básica $X_{2}$ possui o maior valor absoluto entre as varíaveis não básicas, portanto é a nova coluna pivô.
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | Quociente | |
|---|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | -2 | 5 | 0 | 0 | 15000 | - |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 | - |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 | 4000 |
| L4 | 0 | 0 | 2 | -1 | 0 | 1 | 6000 | 3000 |
A linha L4 é a linha pivô, pois possui o menor valor de quociente.
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | Quociente | |
|---|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | -2 | 5 | 0 | 0 | 15000 | - |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 | - |
| L3 | 0 | 0 | 1 | 0 | 1 | 0 | 4000 | 4000 |
| L4 | 0 | 0 | 2 | -1 | 0 | 1 | 6000 | 3000 |
8. Calcular a nova linha Pivô
$ NLP = \displaystyle\frac{1}{pivô}.LP$
$ NLP = \displaystyle\frac{1}{2}.(0,0,2,-1,0,1,6000)$
$ NLP = (0,0,1,-0.5,0,0.5,3000)$
9. Calcular a Segunda Iteração
Mantem-se a nova linha pivô e calcula-se as novas linhas 1, 2 e 3.
A linha 3 não foi modificada, assim permanece associada a variável de folga 2 ($f_{2}$). A linha 1 indica a varível objetivo, a linha 2 representa a variável não básica $X_{1}$, e a linha 4 representa a variável não básica $X_{2}$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | |||||||
| L2 | |||||||
| L3 | |||||||
| L4 | 0 | 0 | 1 | 0.5 | 0 | 0.5 | 3000 |
$NL1 = L1 - coeficiente \,da \,linha1 \,. NLP$
$NL1 = (1,0,-2,5,0,0,15000) - (-2).(0,0,1,-0.5,0,0.5,3000)$
$NL1 = (1,0,-2,5,0,0,15000) + (0,0,2,-1,0,1,6000)$
$NL1 = (1,0,0,4,0,1,21000)$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | 0 | 4 | 0 | 1 | 21000 |
| L2 | |||||||
| L3 | |||||||
| L4 | 0 | 0 | 1 | 0.5 | 0 | 0.5 | 3000 |
Em razão de todas as varíaveis não básicas serem iguaias a zero, indica que a iteração acabou. Outro indicativo de fim de iteração é quando estas variáveis são todas positivas. Assim, não é necessário calcular as linhas 2 e 3, porém, vamos calcular.
$NL2 = L2 - coeficiente \,da \,linha2 \,. NLP$
$NL2 = (0,1,0,1,0,0,3000) - 0.(0,0,1,-0.5,0,0.5,3000)$
$NL2 = (0,1,0,1,0,0,3000)$
$NL3 = L3 - coeficiente \,da \,linha3 \,. NLP$
$NL3 = (0,0,1,0,1,0,4000) - 1.(0,0,1,-0.5,0,0.5,3000)$
$NL3 = (0,0,1,0,1,0,4000) - (0,0,1,-0.5,0,0.5,3000)$
$NL3 = (0,0,0,0.5,1,-0.5,1000)$
| $ Z $ | $ X_{1} $ | $ X_{2} $ | $ f_{1} $ | $ f_{2} $ | $ f_{3} $ | LD | |
|---|---|---|---|---|---|---|---|
| L1 | 1 | 0 | 0 | 4 | 0 | 1 | 21000 |
| L2 | 0 | 1 | 0 | 1 | 0 | 0 | 3000 |
| L3 | 0 | 0 | 0 | 0.5 | 1 | -0.5 | 1000 |
| L4 | 0 | 0 | 1 | 0.5 | 0 | 0.5 | 3000 |
A linha 1 indica que o lucro máximo será de 21.000
As linhas 2 e 4 indicam que as quantidades dos refrigerantes $X_{1}$ e $X_{2}$ que devem ser produzidas para maximinizar o lucro são 3.000 litros de cada.
A linha 3, associada a variável de folga 2, indica que ao final do processo de produção sobrarão 1000 litros do extrato Gama.
Solução usando o Solver do Excel¶